package com.gwcloud.leetcode.hot100;

import java.util.LinkedList;
import java.util.Queue;

/** 
* @ClassName   : Leetcode0200 
* @author      : ganwei 
* @date        : 2020年5月21日 
* @Description : 200. 岛屿数量 
*/
public class Leetcode0200 {
    /**
     * -解决思路
     */
	public int numIslands(char[][] grid) {
		int count = 0;
		for(int i = 0; i < grid.length; i++) {
			for(int j = 0; j < grid[0].length; j++) {
				if(grid[i][j] == '1') {
					bfs(grid, i, j);
					count++;
				}
			}
		}
		
    	return count;
    }
    
	/**
	 * -深度优先遍历
	 */
	public void dfs(char[][] grid, int i, int j) {
		if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
			return;
		}
		dfs(grid, i+1, j);
		dfs(grid, i, j+1);
		dfs(grid, i-1, j);
		dfs(grid, i, j-1);
	}
	
	/**
	 * -广度优先遍历
	 */
	public void bfs(char[][] grid, int i, int j) {
		Queue<int[]> list = new LinkedList<int[]>();
		list.offer(new int[] {i, j});
		while(!list.isEmpty()) {
			int[] cur = list.poll();
			i = cur[0];
			j = cur[1];
            if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
                grid[i][j] = '0';
                list.add(new int[] { i + 1, j });
                list.add(new int[] { i - 1, j });
                list.add(new int[] { i, j + 1 });
                list.add(new int[] { i, j - 1 });
            }			
		}
	}
	
	
    public static void main(String[] args) {
    	
    }
}
